package cn.xmoit.other;

/**
 * 1) 单链表反转 2) 链表中环的检测 3) 两个有序的链表合并 4) 删除链表倒数第n个结点 5) 求链表的中间结点
 *
 * @author fangyy
 */
public class LinkedListDemo {

	/**
	 * 单链表反转
	 * @param list 链表
	 * @return 反转后的新链表
	 */
	public static Node reverse(Node list) {
		Node curr = list, pre = null;
		while (curr != null) {
			Node next = curr.next;
			curr.next = pre;
			pre = curr;
			curr = next;
		}
		return pre;
	}

	/**
	 * 检测环
	 * @param list 链表
	 * @return true or false
	 */
	public static boolean checkCircle(Node list) {
		if (list == null) {
			return false;
		}

		Node fast = list.next;
		Node slow = list;

		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;

			if (slow == fast) {
				return true;
			}
		}

		return false;
	}

	/**
	 * 有序链表合并
	 * @param node1 链表
	 * @param node2 链表
	 * @return 合并后的新链表
	 */
	public Node mergeTwoLists(Node node1, Node node2) {
		// 利用哨兵结点简化实现难度 技巧三
		Node soldier = new Node(0);
		Node p = soldier;

		while (node1 != null && node2 != null) {
			if (node1.data < node2.data) {
				p.next = node1;
				node1 = node1.next;
			}
			else {
				p.next = node2;
				node2 = node2.next;
			}
			p = p.next;
		}

		if (node1 != null) {
			p.next = node1;
		}
		if (node2 != null) {
			p.next = node2;
		}
		return soldier.next;
	}

	/**
	 * 删除倒数第K个结点
	 * @param list 链表
	 * @param k 位置
	 * @return 删除后的新链表
	 */
	public static Node deleteLastKth(Node list, int k) {
		Node fast = list;
		int i = 1;
		while (fast != null && i < k) {
			fast = fast.next;
			++i;
		}

		if (fast == null) {
			return list;
		}

		Node slow = list;
		Node prev = null;
		while (fast.next != null) {
			fast = fast.next;
			prev = slow;
			slow = slow.next;
		}

		if (prev == null) {
			list = list.next;
		}
		else {
			prev.next = prev.next.next;
		}
		return list;
	}

	/**
	 * 求中间结点
	 * @param list 链表
	 * @return 中间结点
	 */
	public static Node findMiddleNode(Node list) {
		if (list == null) {
			return null;
		}

		Node fast = list;
		Node slow = list;

		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}

		return slow;
	}

	/**
	 * 打印链表信息
	 * @param list 链表
	 */
	public static void printAll(Node list) {
		Node p = list;
		while (p != null) {
			System.out.print(p.data + " ");
			p = p.next;
		}
		System.out.println();
	}

	/**
	 * 结点
	 */
	public static class Node {

		private final int data;

		private Node next;

		public Node(int data) {
			this.data = data;
		}

		public Node(int data, Node next) {
			this.data = data;
			this.next = next;
		}

		public int getData() {
			return data;
		}

	}

}